
// RoughHillsGenerator.cpp

// Implements the cRoughHillsGenerator representing a proof-of-concept generator of rough hills

/*
	This is the first iteration of the algorithm. It's only aimed at height generation.
For each chunk, an area of neighboring "hills" is generated, the hills being defined by series of adjacent points with heights.
Each hill is made up of a central point and "petals" that go away from it, each with a random direction and elevation differential.
Then for each block column the distance from the nearest point is calculated and from that the final elevation.
The algorithm is painfully slow, but since its results are less than hoped for, it won't be optimized anyway and is likely to disappera from future MCServer versions.
Further iterations are expected to improve on this algorithm.
*/

#include "Globals.h"
#include "RoughHillsGenerator.h"
#include "ChunkDesc.h"





#define HEIGHT_RANGE      64
#define HILL_SIZE         64
#define PETAL_SIZE        32
#define PI2               6.28318530
#define NEIGHBORHOOD_SIZE 8




class cRoughHillsGenerator::cHill
{
	friend class cRoughHillsGenerator;
	
public:
	cHill(cNoise & a_Noise, int a_BlockX, int a_BlockZ);
	
	void UpdateHeightMap(int a_MinX, int a_MinZ, cChunkDef::HeightMap & a_HeightMap) const;
	
protected:
	class cPoint
	{
	public:
		cPoint(int a_X, int a_Y, int a_Z) :
			m_X(a_X), m_Y(a_Y), m_Z(a_Z)
		{
		}
		
		int m_X;
		int m_Y;
		int m_Z;
	} ;
	
	typedef std::vector<cPoint> cPoints;
	
	cNoise m_Noise;
	cPoints m_Points;
	int m_BlockX;
	int m_BlockZ;
	
	void AddPetal(int a_BlockX, int a_BlockZ, int a_Height, double a_Direction, int a_Size);
	
	#ifdef _DEBUG
	AString ExportAsSVG(int a_Color, int a_OffsetX, int a_OffsetZ) const;
	AString ExportAsTIN(int & a_Count) const;
	#endif  // _DEBUG
} ;





///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// cRoughHillsGenerator:

cRoughHillsGenerator::cRoughHillsGenerator(cChunkGenerator & a_ChunkGenerator) :
	super(a_ChunkGenerator),
	m_Size(HILL_SIZE),
	m_Noise(0)
{
}





cRoughHillsGenerator::~cRoughHillsGenerator()
{
	for (cHills::iterator itr = m_Cache.begin(), end = m_Cache.end(); itr != end; ++itr)
	{
		delete *itr;
	}
	m_Cache.clear();
}





void cRoughHillsGenerator::Initialize(cWorld * a_World, cIniFile & a_IniFile)
{
	super::Initialize(a_World, a_IniFile);
	
	// TODO: Read the seed from INI file
	m_Noise.SetSeed(0);
}





void cRoughHillsGenerator::GenerateBiomes(int a_ChunkX, int a_ChunkZ, cChunkDef::BiomeMap & a_BiomeMap)
{
	for (int i = 0; i < ARRAYCOUNT(a_BiomeMap); i++)
	{
		a_BiomeMap[i] = biExtremeHills;
	}
	
}





void cRoughHillsGenerator::DoGenerate(int a_ChunkX, int a_ChunkZ, cChunkDesc &a_ChunkDesc, cEntityList & a_Entities, cBlockEntityList & a_BlockEntities)
{
	cChunkDef::BiomeMap & BiomeMap = a_ChunkDesc.GetBiomeMap();
	for (int i = 0; i < ARRAYCOUNT(BiomeMap); i++)
	{
		BiomeMap[i] = biExtremeHills;
	}

	cHills CurrentHills;
	GetHillsForChunk(a_ChunkX, a_ChunkZ, CurrentHills);
	
	cChunkDef::HeightMap & HeightMap = a_ChunkDesc.GetHeightMap();
	int MinX = a_ChunkX * cChunkDef::Width;
	int MinZ = a_ChunkZ * cChunkDef::Width;
	for (cHills::const_iterator itr = CurrentHills.begin(), end = CurrentHills.end(); itr != end; ++itr)
	{
		(*itr)->UpdateHeightMap(MinX, MinZ, HeightMap);
	}  // for itr - CurrentHills[]
	
	cChunkDef::BlockTypes & BlockTypes = a_ChunkDesc.GetBlockTypes();
	// TODO: proper terrain composition; only debugging for now:
	for (int z = 0; z < cChunkDef::Width; z++)
	{
		for (int x = 0; x < cChunkDef::Width; x++)
		{
			for (int h = cChunkDef::GetHeight(HeightMap, x, z); h >= 0; h--)
			{
				cChunkDef::SetBlock(BlockTypes, x, h, z, E_BLOCK_STONE);
			}
		}  // for x
	}  // for z
	
	// TODO
}





void cRoughHillsGenerator::GetHillsForChunk(int a_ChunkX, int a_ChunkZ, cHills & a_Hills)
{
	int BaseX = a_ChunkX * cChunkDef::Width / m_Size;
	int BaseZ = a_ChunkZ * cChunkDef::Width / m_Size;
	if (BaseX < 0)
	{
		--BaseX;
	}
	if (BaseZ < 0)
	{
		--BaseZ;
	}
	BaseX -= NEIGHBORHOOD_SIZE / 2;
	BaseZ -= NEIGHBORHOOD_SIZE / 2;
	
	// Walk the cache, move each ravine that we want into a_Ravines:
	int StartX = BaseX * m_Size;
	int EndX = (BaseX + NEIGHBORHOOD_SIZE + 1) * m_Size;
	int StartZ = BaseZ * m_Size;
	int EndZ = (BaseZ + NEIGHBORHOOD_SIZE + 1) * m_Size;
	for (cHills::iterator itr = m_Cache.begin(), end = m_Cache.end(); itr != end;)
	{
		if (
			((*itr)->m_BlockX >= StartX) && ((*itr)->m_BlockX < EndX) &&
			((*itr)->m_BlockZ >= StartZ) && ((*itr)->m_BlockZ < EndZ)
		)
		{
			// want
			a_Hills.push_back(*itr);
			itr = m_Cache.erase(itr);
		}
		else
		{
			// don't want
			++itr;
		}
	}  // for itr - m_Cache[]
	
	for (int x = 0; x < NEIGHBORHOOD_SIZE; x++)
	{
		int RealX = (BaseX + x) * m_Size;
		for (int z = 0; z < NEIGHBORHOOD_SIZE; z++)
		{
			int RealZ = (BaseZ + z) * m_Size;
			bool Found = false;
			for (cHills::const_iterator itr = a_Hills.begin(), end = a_Hills.end(); itr != end; ++itr)
			{
				if (((*itr)->m_BlockX == RealX) && ((*itr)->m_BlockZ == RealZ))
				{
					Found = true;
					break;
				}
			}
			if (!Found)
			{
				a_Hills.push_back(new cHill(m_Noise, RealX, RealZ));
			}
		}
	}
	
	// Copy a_Hills into m_Cache to the beginning:
	cHills HillsCopy(a_Hills);
	m_Cache.splice(m_Cache.begin(), HillsCopy, HillsCopy.begin(), HillsCopy.end());
	
	// Trim the cache if it's too long:
	if (m_Cache.size() > 100)
	{
		cHills::iterator itr = m_Cache.begin();
		std::advance(itr, 100);
		for (cHills::iterator end = m_Cache.end(); itr != end; ++itr)
		{
			delete *itr;
		}
		itr = m_Cache.begin();
		std::advance(itr, 100);
		m_Cache.erase(itr, m_Cache.end());
	}
	
	#ifdef _DEBUG
	AString fnam;
	/*
	// DEBUG: Export as SVG into a file specific for the chunk, for visual verification:
	AString SVG;
	SVG.append("<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<svg xmlns=\"http://www.w3.org/2000/svg\" width=\"1024\" height = \"1024\">\n");
	for (cHills::const_iterator itr = a_Hills.begin(), end = a_Hills.end(); itr != end; ++itr)
	{
		SVG.append((*itr)->ExportAsSVG(0, 512, 512));
	}
	SVG.append("</svg>\n");
	
	Printf(fnam, "roughhills\\%03d_%03d.svg", a_ChunkX, a_ChunkZ);
	{
		cFile File(fnam, cFile::fmWrite);
		if (File.IsOpen())
		{
			File.Write(SVG.c_str(), SVG.size());
		}
	}
	LOGD("SVG written to %s", fnam.c_str());
	SVG.clear();
	//*/
	
	/*
	// DEBUG: Save as TIN into a file specific for the chunk, for visual verification, using Moduler software:
	AString TIN;
	int TotalCount = 0;
	for (cHills::const_iterator itr = a_Hills.begin(), end = a_Hills.end(); itr != end; ++itr)
	{
		int Count = 0;
		TIN.append((*itr)->ExportAsTIN(Count));
		TotalCount += Count;
	}
	
	Printf(fnam, "roughhills\\%03d_%03d.tin", a_ChunkX, a_ChunkZ);
	{
		cFile File(fnam, cFile::fmWrite);
		if (File.IsOpen())
		{
			AString Header;
			Printf(Header, "%d\n", TotalCount);
			File.Write(Header.c_str(), Header.length());
			File.Write(TIN.c_str(), TIN.size());
		}
	}
	LOGD("TIN written to %s", fnam.c_str());
	TIN.clear();
	//*/
	#endif  // _DEBUG
}





///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// cRoughHillsGenerator::cHill:

cRoughHillsGenerator::cHill::cHill(cNoise & a_Noise, int a_BlockX, int a_BlockZ) :
	m_Noise(a_Noise),
	m_BlockX(a_BlockX),
	m_BlockZ(a_BlockZ)
{
	m_Points.reserve(PETAL_SIZE * 4);
	
	// Pick a direction and size:
	int Rnd = m_Noise.IntNoise2DInt(a_BlockX, a_BlockZ) / 11;
	int NumPetals = 2 + (4 / ((Rnd & 7) + 1));  // Have 2 to 6 petals, with strong preference of lower numbers
	Rnd = Rnd / 8;
	int Height = 96 + (Rnd % HEIGHT_RANGE);
	Rnd = Rnd / HEIGHT_RANGE;
	int x = a_BlockX + (Rnd % HILL_SIZE) - (HILL_SIZE / 2);
	Rnd = Rnd / HILL_SIZE;
	int z = a_BlockZ + (Rnd % HILL_SIZE) - (HILL_SIZE / 2);
	Rnd = Rnd / HILL_SIZE;
	for (int i = 0; i < NumPetals; i++)
	{
		int Rnd2 = m_Noise.IntNoise3DInt(a_BlockX, a_BlockZ, i * 17) / 19;
		double Direction = PI2 * (128 * i + (Rnd2 % 64)) / (NumPetals * 128);
		Rnd2 = Rnd2 / 64;
		AddPetal(x, z, Height, Direction, PETAL_SIZE + (Rnd2 % PETAL_SIZE));
	}
}





void cRoughHillsGenerator::cHill::AddPetal(int a_BlockX, int a_BlockZ, int a_Height, double a_Direction, int a_Size)
{
	int Rnd = m_Noise.IntNoise3DInt(a_BlockX * 13, a_BlockZ + 19, (int)(a_Direction * 50.0) + a_Size) / 7;
	int HDif = -256;  // The slope in which the petal is "gaining" height, as a 1024-fixed-point number (1024 equals 1 block per step)
	int XDif = (int)(1024 * sin(a_Direction));
	int ZDif = (int)(1024 * cos(a_Direction));
	int MicroX = 0, MicroZ = 0, MicroH = a_Height * 1024;  // X, Y, Height as 1024-fixed-point number
	int OldX = 1024;
	int OldZ = 1024;
	int XDif2 = 0;
	int ZDif2 = 0;
	int HDif2 = 0;
	for (int i = 0; i < a_Size;)
	{
		XDif += XDif2;
		ZDif += ZDif2;
		HDif += ZDif2;
		MicroX += XDif;
		MicroZ += ZDif;
		MicroH += HDif;
		int Rnd2 = m_Noise.IntNoise3DInt(MicroX + 50, MicroZ + i, MicroH + i) / 13;
		XDif2 = 16 * ((Rnd2 % 64) - 32);
		Rnd2 = Rnd2 / 64;
		ZDif2 = 16 * ((Rnd2 % 64) - 32);
		Rnd2 = Rnd2 / 64;
		HDif2 = 4 * ((Rnd2 % 64) - 32);
		
		if (XDif > 1536)
		{
			XDif2 -= 256;
		}
		else if (XDif < -1536)
		{
			XDif2 += 256;
		}
		if (ZDif > 1536)
		{
			ZDif2 -= 256;
		}
		else if (ZDif < -1536)
		{
			ZDif2 += 256;
		}
		
		int NewX = MicroX / 1024;
		int NewZ = MicroZ / 1024;
		if ((NewX == OldX) && (NewZ == OldZ))
		{
			// Same coords as the previous point, skip it
			continue;
		}
		OldX = NewX;
		OldZ = NewZ;
		m_Points.push_back(cPoint(a_BlockX + NewX, MicroH / 1024, a_BlockZ + NewZ));
		i++;
	}
}





void cRoughHillsGenerator::cHill::UpdateHeightMap(int a_MinX, int a_MinZ, cChunkDef::HeightMap & a_HeightMap) const
{
	for (int x = 0; x < cChunkDef::Width; x++)
	{
		int BlockX = a_MinX + x;
		for (int z = 0; z < cChunkDef::Width; z++)
		{
			int BlockZ = a_MinZ + z;
			int CurHeight = cChunkDef::GetHeight(a_HeightMap, x, z);
			for (cPoints::const_iterator itr = m_Points.begin(), end = m_Points.end(); itr != end; ++itr)
			{
				int PtHeight = itr->m_Y - (int)sqrt((double)((itr->m_X - BlockX) * (itr->m_X - BlockX) + (itr->m_Z - BlockZ) * (itr->m_Z - BlockZ)));
				if (CurHeight < PtHeight)
				{
					CurHeight = PtHeight;
				}
			}  // for itr - m_Points[]
			cChunkDef::SetHeight(a_HeightMap, x, z, CurHeight);
		}  // for z
	}  // for x
}





#ifdef _DEBUG
AString cRoughHillsGenerator::cHill::ExportAsSVG(int a_Color, int a_OffsetX, int a_OffsetZ) const
{
	AString SVG;
	//*
	// Export as individual points:
	for (cPoints::const_iterator itr = m_Points.begin(), end = m_Points.end(); itr != end; ++itr)
	{
		AppendPrintf(SVG, "<path style=\"fill:none;stroke:#%06x;stroke-width:1px;\" d=\"M %d %d L %d %d\"/>\n",
			itr->m_Y, a_OffsetX + itr->m_X - 1, a_OffsetZ + itr->m_Z, a_OffsetX + itr->m_X + 1, a_OffsetZ + itr->m_Z
		);
		AppendPrintf(SVG, "<path style=\"fill:none;stroke:#%06x;stroke-width:1px;\" d=\"M %d %d L %d %d\"/>\n",
			itr->m_Y, a_OffsetX + itr->m_X, a_OffsetZ + itr->m_Z - 1, a_OffsetX + itr->m_X, a_OffsetZ + itr->m_Z + 1
		);
  }
  //*/
  
  /*
  // Export as lines (will get a few false positives on petal transitions):
	AppendPrintf(SVG, "<path style=\"fill:none;stroke:#%06x;stroke-width:1px;\"\nd=\"M %d %d\n", a_Color, a_OffsetX + m_Points.front().m_X, a_OffsetZ + m_Points.front().m_Z);
	for (cPoints::const_iterator itr = m_Points.begin(), end = m_Points.end(); itr != end; ++itr)
	{
		AppendPrintf(SVG, "L %d %d\n",
			a_OffsetX + itr->m_X, a_OffsetZ + itr->m_Z
		);
  }
  SVG.append("\" />\n");
  //*/
  
  // Base point highlight:
  AppendPrintf(SVG, "<path style=\"fill:none;stroke:#ff0000;stroke-width:1px;\" d=\"M %d,%d L %d,%d\"/>\n",
		a_OffsetX + m_BlockX - 5, a_OffsetZ + m_BlockZ, a_OffsetX + m_BlockX + 5, a_OffsetZ + m_BlockZ
	);
  AppendPrintf(SVG, "<path style=\"fill:none;stroke:#ff0000;stroke-width:1px;\" d=\"M %d,%d L %d,%d\"/>\n",
		a_OffsetX + m_BlockX, a_OffsetZ + m_BlockZ - 5, a_OffsetX + m_BlockX, a_OffsetZ + m_BlockZ + 5
	);

	return SVG;	
}





AString cRoughHillsGenerator::cHill::ExportAsTIN(int & a_Count) const
{
	/*
	TIN format is really simple. It is a text-based format, the first line specifying the number of points (decimal number),
	then on each line one point's coords are given, as X, Y, Height.
	*/
	AString res;
	a_Count = m_Points.size();
	for (cPoints::const_iterator itr = m_Points.begin(), end = m_Points.end(); itr != end; ++itr)
	{
		AppendPrintf(res, "%d %d %d\n", itr->m_X, itr->m_Z, itr->m_Y);
	}  // for itr - m_Points[]
	return res;
}
#endif  // _DEBUG



